#include<iostream>
using namespace std;
#include<queue>
  struct ListNode {
      int val;
      ListNode *next;
      ListNode() : val(0), next(nullptr) {}
      ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
  };
class Solution {
public:
    class cmp {
    public:
        bool operator()(ListNode* a1, ListNode* a2) {
            return a1->val > a2->val;
        }
    };
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> que;
        for (auto& e : lists)
            if (e)
                que.push(e);
        if (que.empty())
            return nullptr;
        ListNode* ans = que.top(), * help = ans;
        if (que.top()->next)
            que.push(que.top()->next);
        que.pop();
        while (!que.empty()) {
            if (que.top()->next)
                que.push(que.top()->next);
            help->next = que.top();
            help = help->next;
            que.pop();
        }
        return ans;
    }
};